package com.epam.mycollections.lists;

import com.epam.mycollections.interfaces.MyList;
import java.util.Comparator;
import java.util.RandomAccess;


/**
 * My Personal Collection
 *
 * @author Iurii Miedviediev
 * @version 1.0 Build 06.04.2014
 *
 */
public class MyCollections {

    private static final int DIVISOR = 2;

    private MyCollections() {
    }

    //Helper, recursive implementation of the Quick Sort with Comparator
    private static <E> MyList<E> quickSortComparator(MyList<E> list, Comparator<E> c) {

        //base case
        if(list.size() <= 1) {
            return list;
        } else {
            //holders for elements less and bigger (or equal) than the pivot
            MyList<E> less = new MyLinkedList();
            MyList<E> bigger = new MyLinkedList();
            E pivot = list.get(0);

            //sorting the elements
            for(int pos=1, length = list.size(); pos<length; pos++) {
                E current = list.get(pos);
                if(c.compare(current,pivot) < 0) {
                    less.add(current);
                } else {
                    bigger.add(current);
                }
            }
            //recursively sort less and bigger elements
            less = quickSortComparator(less, c);
            bigger = quickSortComparator(bigger, c);

            //merge all the results and return result
            less.add(pivot);
            copy(less,bigger);
            return less;
        }
    }

    //Helper, recursive implementation of the Quick Sort with Comparable
    private static <E extends Comparable<E>> MyList<E> quickSort(MyList<E> list) {

        //base case
        if(list.size() <= 1) {
            return list;
        } else {
            //holders for elements less and bigger (or equal) than the pivot
            MyList<E> less = new MyLinkedList();
            MyList<E> bigger = new MyLinkedList();
            E pivot = list.get(0);

            //sorting the elements
            for(int pos=1, length = list.size(); pos<length; pos++) {
                E current = list.get(pos);
                if(current.compareTo(pivot) < 0) {
                    less.add(current);
                } else {
                    bigger.add(current);
                }
            }
            //recursively sort less and bigger elements
            less = quickSort(less);
            bigger = quickSort(bigger);

            //merge all the results and return result
            less.add(pivot);
            copy(less,bigger);
            return less;
        }
    }

    //Helper method, implementation of BubbleSort with Comparator
    private static <E> void bubbleSortComparator(MyList<E> list, Comparator<E> c) {
        if(list.size() <= 1) {
            return;
        }
        boolean sorted = false;
        while(!sorted) {
            sorted = true;
            for(int pos=0,length=list.size(); pos<length-1; pos++) {
                if(c.compare(list.get(pos), list.get(pos+1)) > 0) {
                    sorted = false;
                    swap(list, pos, pos+1);
                }
            }
        }
    }

    //Helper method, implementation of BubbleSort with Comparable
    private static <E extends Comparable<E>> void bubbleSort(MyList<E> list) {
        if(list.size() <= 1) {
            return;
        }
        boolean sorted = false;
        while(!sorted) {
            sorted = true;
            for(int pos=0,length=list.size(); pos<length-1; pos++) {
                if((list.get(pos)).compareTo(list.get(pos+1)) > 0) {
                    sorted = false;
                    swap(list, pos, pos+1);
                }
            }
        }
    }

    /**
     * Sort MyList
     * Use either Recursive QuickSort algorithm (for MyArrayList) or
     * BubbleSort for MyLinkedList
     *
     * @param list	MyList to be sorted
     */
    public static <E extends Comparable<E>> void sort(MyList<E> list) {
        if(list instanceof RandomAccess) {
            MyList<E> newList = quickSort(list);
            clone(list,newList);
        } else {
            bubbleSort(list);
        }
    }

    /**
     * Sort MyList, using Comparator
     * Use either Recursive QuickSort algorithm (for MyArrayList) or
     * BubbleSort for MyLinkedList
     *
     * @param list      MyList to be sorted
     * @param c         Object with Comparator interface realization
     */
    public static <E> void sort(MyList<E> list, Comparator<E> c) {
        if(list instanceof RandomAccess) {
            MyList<E> newList = quickSortComparator(list, c);
            clone(list,newList);
        } else {
            bubbleSortComparator(list, c);
        }
    }

    /**
     * Swaps the elements at the specified positions in the specified list
     * @param list	Source MyList
     * @param i		Position of the first element to swap
     * @param j		Position of the second element to swap
     */
    public static <E> void swap(MyList<E> list, int i, int j) {

        //restrict using negative or too large indexes
        if(i > list.size()-1 || i < 0 || j > list.size()-1 || j < 0) {
            throw new IllegalArgumentException("Incorrect index for MyList");
        }
        //remember element at position i
        E temp = list.get(i);

        //swap elements
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    /**
     * Copy (Append) all of the elements from one MyList into another
     * @param dest	Destination MyList
     * @param src	Source MyList
     */
    public static <E> void copy(MyList<E> dest, MyList<E> src) {
        for(int pos=0, length=src.size(); pos<length; pos++) {
            dest.add(src.get(pos));
        }
    }

    /**
     * Clone (Replace) all of the elements from one MyList into another
     * @param dest	Destination MyList
     * @param src	Source MyList
     */
    public static <E> void clone(MyList<E> dest, MyList<E> src) {
        if(dest.size() != src.size()) {
            throw new IllegalArgumentException("Given lists have different capacity");
        } else {
            for(int pos=0, length=src.size(); pos<length; pos++) {
                dest.set(pos, src.get(pos));
            }
        }
    }

    /**
     * Reverses the order of the elements in the specified list
     * @param list 		MyList to be reversed
     */
    public static <E> void reverse(MyList<E> list) {

        //holder for the new reversed MyLinkedList
        MyList<E> reversed = new MyArrayList();

        //Go from the back of the List and add elements to the holder
        for(int pos=list.size()-1; pos>=0; pos--) {
            reversed.add(list.get(pos));
        }
        clone(list,reversed);
    }

    /**
     * Binary search on MyList
     *
     * @param list		MyList, field to search
     * @param key		element to find
     * @return		index of desirable element or (-(insertion point) - 1), if element is not in the List
     */
    public static <E extends Comparable<E>> int binarySearch(MyList<E> list, E key) {
        return bisectionSearch(list, key, 0, list.size());
    }

    //Helper for binarySearch
    private static <E extends Comparable<E>> int bisectionSearch(MyList<E> list, E key, int minIndex, int maxIndex) {

        //possible position of desirable element
        int midIndex = (minIndex + maxIndex) / DIVISOR;

        //if element was not found
        if(minIndex >= maxIndex) {
            return -(midIndex) - 1;
        }

        //if element is possibly in the left part of the List, drop the right part
        if(list.get(midIndex).compareTo(key) > 0) {
            return bisectionSearch(list, key, minIndex, midIndex);
        } else if(list.get(midIndex).compareTo(key) < 0) {
            return bisectionSearch(list, key, midIndex+1, maxIndex);
        } else {
            return midIndex;
        }
    }

}

